//Given an encoded string, return its decoded string. 
//
// The encoding rule is: k[encoded_string], where the encoded_string inside the 
//square brackets is being repeated exactly k times. Note that k is guaranteed to 
//be a positive integer. 
//
// You may assume that the input string is always valid; No extra white spaces, 
//square brackets are well-formed, etc. 
//
// Furthermore, you may assume that the original data does not contain any 
//digits and that digits are only for those repeat numbers, k. For example, there 
//won't be input like 3a or 2[4]. 
//
// 
// Example 1: 
// Input: s = "3[a]2[bc]"
//Output: "aaabcbc"
// Example 2: 
// Input: s = "3[a2[c]]"
//Output: "accaccacc"
// Example 3: 
// Input: s = "2[abc]3[cd]ef"
//Output: "abcabccdcdcdef"
// Example 4: 
// Input: s = "abc3[cd]xyz"
//Output: "abccdcdcdxyz"
// 
// 
// Constraints: 
//
// 
// 1 <= s.length <= 30 
// s consists of lowercase English letters, digits, and square brackets '[]'. 
// s is guaranteed to be a valid input. 
// All the integers in s are in the range [1, 300]. 
// 
// Related Topics String Stack Recursion 👍 6169 👎 271


package leetcode.editor.en;

import java.util.LinkedList;

public class _394_DecodeString {
    public static void main(String[] args) {
        Solution solution = new _394_DecodeString().new Solution();
        String s = solution.decodeString("3[a2[c]]");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String decodeString(String s) {
            StringBuilder r = new StringBuilder();
            int multi = 0;
            LinkedList<Integer> multiStack = new LinkedList<>();
            LinkedList<String> resStack = new LinkedList<>();

            for (char c : s.toCharArray()) {
                if (c == '[') {
                    multiStack.addLast(multi);
                    resStack.addLast(r.toString());
                    r = new StringBuilder();
                    multi = 0;
                }else if (c == ']'){
                    StringBuilder temp = new StringBuilder();
                    Integer curMulti = multiStack.removeLast();
                    for (int i = 0; i < curMulti; i++) {
                        temp.append(r);
                    }
                    r = new StringBuilder(resStack.removeLast()+temp);
                }else if (c>='0' &&c<='9'){
                    multi = multi*10 +Integer.parseInt(c+"");
                }else {
                    r.append(c);
                }
            }
            return r.toString();
        }
        public String decodeString1(String s) {
            StringBuilder res = new StringBuilder();
            int multi = 0;
            LinkedList<Integer> stack_multi = new LinkedList<>();
            LinkedList<String> stack_res = new LinkedList<>();
            for(Character c : s.toCharArray()) {
                if(c == '[') {
                    stack_multi.addLast(multi);
                    stack_res.addLast(res.toString());
                    multi = 0;
                    res = new StringBuilder();
                }
                else if(c == ']') {
                    StringBuilder tmp = new StringBuilder();
                    int cur_multi = stack_multi.removeLast();
                    for(int i = 0; i < cur_multi; i++) tmp.append(res);
                    res = new StringBuilder(stack_res.removeLast() + tmp);
                }
                else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
                else res.append(c);
            }
            return res.toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}